#include<stdio.h>
struct id
{
   int row;
   int col;
   int num;
   int process[9];
};
int process(int (*pans) [9][9],struct id (*pa)[81],int (*ppbForAll)[9][9][10],int obForAll[9][9][10],int n,int cur)
{
   int tea;
   int i,j,p,q;
   int t;
   int x,y;
   int tx,ty;
   int temp[9][9][10];
   int teee;
   int newObForAll[9][9][10];
   int firstForAll[9][9];
  if(cur==n)
  {
   for(i=0;i<9;i++)
      for(j=0;j<9;j++)
         if(j!=8)
            printf("%d ",(*pans)[i][j]);
         else
            printf("%d\n",(*pans)[i][j]);     
   printf("\n");  
  }
  else
  {
     if((*pa)[cur].num==0)
      return -1;
      x=(*pa)[cur].row;
      y=(*pa)[cur].col;

      for(i=0;i<(*pa)[cur].num;i++)
      {
         for(q=0;q<9;q++)
            for(j=0;j<9;j++)
               firstForAll[q][j]=0;
         for(q=0;q<9;q++)
            for(j=0;j<9;j++)
               for(t=0;t<10;t++)
                  newObForAll[q][j][t]=obForAll[q][j][t];
         t=(*pa)[cur].process[i];
         if((*ppbForAll)[x][y][t]==1)
            continue;
         for(j=0;j<9;j++)
         {
            if(firstForAll[x][j]==0)
            {
               firstForAll[x][j]=1;
               if((*ppbForAll)[x][j][t]==0)           
                  (*ppbForAll)[x][j][t]=1;
               else
                  newObForAll[x][j][t]=1; 
            }
         }   
         for(j=0;j<9;j++)
         { 
            if(firstForAll[j][y]==0)
            {
               firstForAll[j][y]=1;
               if((*ppbForAll)[j][y][t]==0)           
                  (*ppbForAll)[j][y][t]=1;
               else
                  newObForAll[j][y][t]=1; 
            }
         }  
         tx=x/3;
         ty=y/3;
         for(j=3*tx;j<=3*tx+2;j++)
            for(p=3*ty;p<=3*ty+2;p++)
            {
               if(firstForAll[j][p]==0)
               {
                  firstForAll[j][p]=1;
                  if((*ppbForAll)[j][p][t]==0)
                  (*ppbForAll)[j][p][t]=1;
                  else
                  newObForAll[j][p][t]=1; 
               }
            }
         (*pans)[x][y]=t;
         //  for(teee=0;teee<9;teee++)
         //    for(j=0;j<9;j++)
         // if(j!=8)
         //    printf("%d ",(*pans)[teee][j]);
         // else
         //    printf("%d\n",(*pans)[teee][j]);     
         // printf("\n");  
         process(pans,pa,ppbForAll,newObForAll,n,cur+1);
         (*pans)[x][y]=0;
         for(j=0;j<9;j++)
            (*ppbForAll)[x][j][t]=newObForAll[x][j][t];      
         for(j=0;j<9;j++)
             (*ppbForAll)[j][y][t]=newObForAll[j][y][t];
           
         for(j=3*tx;j<=3*tx+2;j++)
            for(p=3*ty;p<=3*ty+2;p++)
              (*ppbForAll)[j][p][t]=newObForAll[j][p][t];      
      } 
  }
  return 0;
}
int main()
{
   FILE *fp;
   char str[20];
   int puzzle[9][9];
   int pbForRow9[9][10];
   int pbForChild9[9][10];
   int pbForColumn9[9][10];
   int ans[9][9];
   fp = fopen("puzzle.txt" , "r");
   if(fp == NULL) {
      perror("打开文件时发生错误");
      return(-1);
   }
   
   int i;
   int j;
   int t=0;
   //input
   for(i=0;i<9;i++)
   {
      t=0;
      if( fgets (str, 20, fp)!=NULL ) 
      {
         for(j=0;j<20;j++)
         {
            if(str[j]=='\0')
             break;
            puzzle[i][t]=str[j]-'0';
            t++;
            if(str[j+1]!='\0')
            j++;
         }
      }
   }
   // test
   // for(i=0;i<9;i++)
   //    for(j=0;j<9;j++)
   //       if(j!=8)
   //          printf("%d ",puzzle[i][j]);
   //       else
   //          printf("%d\n",puzzle[i][j]);       
    for(i=0;i<9;i++)
      for(j=0;j<10;j++)
      {
           pbForRow9[i][j]=0;
           pbForColumn9[i][j]=0;
           pbForChild9[i][j]=0;
      }
    for(i=0;i<9;i++)
      for(j=0;j<9;j++)
         ans[i][j]=0;
   fclose(fp);
   //validate
   int t2;
   for(i=0;i<9;i++)
   {
      for(j=0;j<9;j++)
      {
         t=puzzle[i][j];
         if(t==0)
            continue;
         if(pbForRow9[i][t]==1)
         {
            printf("No Answer\n");
            return -1;
         }   
         if(pbForColumn9[j][t]==1)
         {
            printf("No Answer\n");
            return -1;
         }
         t2=3*(i/3)+j/3;  
         if(pbForChild9[t2][t]==1)
         {
            printf("No Answer\n");
            return -1;
         }   
         pbForRow9[i][t]=1;


         pbForColumn9[j][t]=1;


         pbForChild9[t2][t]=1;


         ans[i][j]=t;     
      }
   }
   //preprocess
   int pbForAll[9][9][10];
   for(i=0;i<9;i++)
      for(j=0;j<9;j++)
         for(t=0;t<10;t++)
           pbForAll[i][j][t]=0;

   struct id a[81];
   int n=0;
   int numCount=0;
   for(i=0;i<9;i++)
      for(j=0;j<9;j++)
      {
         numCount=0;
         if(puzzle[i][j]!=0)
         {
            pbForAll[i][j][puzzle[i][j]]=1;
            continue;
         }  
         t2=3*(i/3)+j/3;  
         for(t=1;t<=9;t++)
         {
            if(pbForRow9[i][t]==1)
            {
               pbForAll[i][j][t]=1;
               continue;
            }
            if(pbForColumn9[j][t]==1)
            {
               pbForAll[i][j][t]=1;
               continue;
            }   
            if(pbForChild9[t2][t]==1)
            {
               pbForAll[i][j][t]=1;
               continue;
            }  
         }
         a[n].row=i;
         a[n].col=j;

         for(t=1;t<=9;t++)
         {
            if(pbForAll[i][j][t]==0)
            {
               a[n].process[numCount]=t;
               numCount++;
            }
         }
         a[n].num=numCount;
         n++;
      }
   //preprocess - sort a
   struct id temp;
   for(i=0;i<n;i++)
      for(j=0;j<n-i-1;j++)
         if(a[j].num>a[j+1].num)
         {
            temp=a[j];
            a[j]=a[j+1];
            a[j+1]=temp;
         }
   //process
   int (*pans)[9][9]=&ans;
   int (*ppbForAll)[9][9][10]=&pbForAll;
   struct id (*pa)[81]=&a;
  
   int obForAll[9][9][10];
   for(i=0;i<9;i++)
      for(j=0;j<9;j++)
         for(t=0;t<10;t++)
           obForAll[i][j][t]=pbForAll[i][j][t];
   process(pans,pa,ppbForAll,obForAll,n,0);
     
   return 0;
}